package lowest_common_ancestor_of_a_binary_tree;

import java.util.Stack;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }

        TreeNode ret1 = lowestCommonAncestor(root.left, p, q);
        TreeNode ret2 = lowestCommonAncestor(root.right, p, q);

        if (ret1 != null && ret2 != null) {
            return root;
        } else if (ret1 == null) {
            return ret2;
        } else return ret1;
    }

    private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if (root == null || node == null) {
            return false;
        }


        stack.push(root); //root不为空放入栈中

        if (root == node) {
            return true;
        }

        //遍历左树
        boolean flg1 = getPath(root.left, node, stack);
        if (flg1) {
            return true;
        }

        boolean flg2 = getPath(root.right, node, stack);
        if (flg2) {
            return true;
        }

        stack.pop();
        return false;
    }

    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        Stack<TreeNode> Pstack = new Stack<>();
        Stack<TreeNode> Qstack = new Stack<>();

        getPath(root, p, Pstack);
        getPath(root, q, Qstack);

        int size1 = Pstack.size();
        int size2 = Qstack.size();

        if (size1 > size2) {
            int size = size1 - size2;
            while (size != 0) {
                Pstack.pop();
                size--;
            }
        } else {
            int size = size2 - size1;
            while (size != 0) {
                Qstack.pop();
                size--;
            }
        }

        while (!Pstack.isEmpty() && !Qstack.isEmpty()) {
            if (Pstack.peek() == Qstack.peek()) {
                return Pstack.peek();
            } else {
                Pstack.pop();
                Qstack.pop();
            }
        }
        return null;
    }
}